home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / tex / sortdemo.zip / SORTDEMO.DOC < prev   
Text File  |  1987-09-03  |  3KB  |  65 lines
  1.    Graphic Illustration of Sorting Algorithms     K.L. Noell 03.Sep.87
  2.  
  3.  
  4. It's difficult to explain sorting algorithms merely by verbose descrip-
  5. tions.  They are either easy to understand and simple to design but
  6. they are very slow and inefficient;  or they run fairly quick but their
  7. design and implementation is rather complex and troublesome.
  8.  
  9. For teaching purpose I have realized an idea which illustrates various
  10. sorting algorithms with the aid of real-time animated pixel graphics.
  11. Keys to be sorted are 640 random integers distributed over the inter-
  12. val [0...199].  These elements are stored in an array which is mapped
  13. to corresponding screen pixels ( x:[0...639], y:[0...199] ).
  14.  
  15. In the beginning, this pixel distribution looks like a starry sky. After
  16. the sorting procedure is started, you can watch its progress directly.
  17. Swapping and moving of elements effects appropriate pattern updates by
  18. shifting the pixels towards their final ascending order.  Depending on
  19. the particular sorting strategy, this works very slow and fussy or it is
  20. intelligible sophisticated and quick.  You can compare features and
  21. performance of different sorting algorithms;  after processing the
  22. randomly distributed keys, the sorting can be started once more to deal
  23. with an array already sorted, but in opposite (descending) order which
  24. means sometimes the worst case.  The frequencies of swaps and loops
  25. (comparisons) are counted.
  26.  
  27. Turbo-Pascal programs are provided to demonstrate the following sorting
  28. algorithms:
  29.  
  30. BubbleSort,  HeapSort,  LinearSort,  QuickSort,  ShakeSort,  ShellSort .
  31.  
  32.  
  33. My examples are based on sorting algorithms from the following books:
  34.  
  35. A.V. Aho; J.E. Hopcroft; J.D. Ullman:  Data Structures and Algorithms.
  36.           Addison-Wesley, Amsterdam etc (1983)
  37.  
  38. Sara Baase: Computer Algorithms: Introduction to Design and Analysis.
  39.           Addison-Wesley, Amsterdam etc (1978)
  40.  
  41.  
  42. I have written and tested these programs with Turbo-Pascal (3.01A) under
  43. DOS 3.1, running in an IBM-AT02 and also in clones with CGA and EGA.
  44.  
  45.  
  46.                   ===>  Disclaimer Notice  <===
  47.  
  48.        This SORTDEMO - package is provided for educational
  49.        purpose.  Neither the author nor the distributor makes
  50.        any warranty or assumes any liability or responsibility
  51.        for accuracy, completeness or usefulness.
  52.        All risk of use is on the user.
  53.        It may be freely copied but may not be sold for profit.
  54.        Please keep the credits which refer to author and provenance.
  55.  
  56.  
  57. Suggestions, problems:  please send E-mail to  NOELL@DWIFH1.BITNET
  58.  
  59.                         or contact:            Prof.Dr. Karl-L. Noell
  60.                                                FHW - FB MND
  61.                                                Am Brueckweg 26
  62.                                                D-6090 Ruesselsheim
  63.                                                (W. Germany)
  64.  
  65.